「学习总结」正睿 计数选讲

📅 Last Updated: 2021-02-01
📊 Word Count: 632
⏱️ Estimated Reading Time: 4 minutes
📄 PDF 📝 Source

wzy哥哥的一些有趣计数题~

例题壹

给定 n,mn, m ，构造 nn 堆石子，每堆石子的数量 ∈[1,2m−1]\in[1, 2^m-1]，每堆石子数目互不相同。求使得 Nim 先手必胜的构造方案数。

n≤107,m≤109n\le 10^7, m\le 10^9 模数：109+710^9 + 7

考虑直接后手必胜的情况，即长度为 nn 的序列，异或和为 00。

设长度为 nn 的方案数为 f(n)f(n)。能够得到如下递推式： f(n)=(2m−1)(2m−2)(2m−3)⋯(2m−n+1)−f(n−1)−(2m−1)(i−1)f(n−2) f(n) = (2^m-1)(2^m-2)(2^m-3) \cdots(2^m - n+1)\\ -f(n - 1)\\ -(2^m-1)(i-1)f(n-2) 考虑到前 (n−1)(n-1) 位置个随意填上互不相同的值域为 [1,2m−1][1, 2^m-1] 的数字。然后减去前面正好填出异或和为 00 的方案（因为最后一个位置还要填数字）（即：f(n−1)f(n-1)）。理论上，最后一个数字应该等于前面 (n−1)(n - 1) 数字的异或和，但是可能不满足互不相同的条件，先枚举不合法的方案最后一个数字是什么，然后枚举和前面哪一个冲突，再乘上 f(n−2)f(n-2)。

例题贰

给出 nn 个正整数 aia_i，选出 nn 个正整数 bib_i ，nn 个正整数 did_i，满足

∀i∈[1,n],di∣bi∣ai\forall i \in [1, n], d_i|b_i|a_i，求有多少种选法满足 ∏indi2≥∏i=1nbi\prod_{i}^n d_i^2 \ge \prod_{i=1}^{n}b_i

n≤100,ai≤109​n\le 100, a_i \le 10^9​

对于任意一种方案 ∏i=1ndi2>∏i=1nbi​\prod_{i=1}^{n}d_i^2 > \prod_{i=1}^{n}b_i​

试想把所有 did_i 取成 bidi\frac{b_i}{d_i}，即： ∏i=1nbi2di2>∏i=1nbi\prod_{i=1}^{n} \frac{b_i^2}{d_i^2} > \prod_{i=1}^{n}b_i

即： ∏i=1ndi2<∏i=1nbi​\prod_{i=1}^{n}d_i^2 < \prod_{i=1}^{n}b_i​

所以其实 ∏i=1ndi2<∏i=1nbi\prod_{i=1}^{n}d_i^2 < \prod_{i=1}^{n}b_i 和 ∏i=1ndi2>∏i=1nbi\prod_{i=1}^{n}d_i^2 > \prod_{i=1}^{n}b_i 的方案是一一对应的。

只需要求出 ∏i=1ndi2=bi\prod_{i=1}^{n}d_i^2=b_i 的方案数即可。这个可以对每一个质因子单独 dp。

例题叁

CF383D

nn 个位置排成一排,有 mm 个人依次进场选位置,每个人一开始选一个方向,从左到右/从右到左,并选择一个位置,然后按照她选择的方向进入场地,走到这个位置,如果有人,就继续按当前方向往后寻找,知道找到一个空位坐下,如果没有空位,他就会生气.

为每个人确定一个方向和选择的位置。求没有人生气的方案数。

考虑把序列首尾之间连接一个点 n+1n+1 转化成一个环，相当于每个人选择一个位置，然后选择一个方向转圈，方案不合法，当且仅当有一个人占据了 n+1n+1 这个位置。

因为是一个环，所以任意一个位置都是等价的，所以任意一个位置有人的概率为 (1−mn+1)​(1 -\frac{m}{n+1})​

答案就是 (1−mn+1)2m(n+1)m(1 - \frac{m}{n + 1})2^m(n + 1) ^ m

例题肆

「杂题记录」「CTSC2017」吉夫特

例题伍

「杂题记录」括号序列（格路计数）

例题陆

一棵树，每条边的两个端点的大小关系给出，形如 au>ava_u > a_v 或者 au<ava_u < a_v。求有多少种满足条件的排列 aa 。 n≤5000n \le 5000

例题柒

给定一个字符串 SS，仅包含 < 和 > 两种字符。

你需要计算「使得 pi<pi+1p_i < p_{i+1} 当且仅当 sis_i为 < 的排列 p1,p2,⋯pn+1p_1, p_2, \cdots p_{n+1} 」的数量。

可以发现，答案可能很大，因此你只要输出它对 998244353998244353 取模的结果。

巧妙容斥。

先不考虑所有 > 的限制，只考虑 < 的限制，> 处的偏序关系任意，将一段 < 视为连续的一段，设每一连续的一段长度为 aia_i ，这样的方案数就是 n!∏iai!\frac{n!}{\prod_{i}a_i!}。

然后显然答案需要减去任意位置为 < 的情况，对这个 < 满足数量容斥即可。

考虑设 f(n)f(n) 表示只考虑前 nn 个数字方案数。

考虑 f(n)f(n) 的答案和 f(n−1)f(n-1) 的答案的差别，枚举最后一段有多长即可。 f(n)=∑i=1i−1[Sj=′>′](i−j)!f(i)(−1)cnti−1−cntj f(n) = \sum_{i=1}^{i-1}\frac{[S_j = '>']}{(i-j)!}f(i)(-1)^{cnt_{i-1}-cnt_{j}} 这东西可以分治 NTT​NTT​ 优化。

例题玐

nn 阶 循环矩阵是一种形如： A=[a0an−1⋯a2a1a1a0an−1a2⋮a1a0⋱⋮an−2⋱⋱an−1an−1an−2⋯a1a0] A=\begin{bmatrix} a_0 & a_{n-1} &\cdots & a_2 & a_1\\ a_1 & a_{0} &a_{n-1} & & a_2\\ \vdots & a_1 &a_0 & \ddots & \vdots\\ a_{n-2} & &\ddots & \ddots & a_{n-1}\\ a_{n-1} & a_{n-2} &\cdots & a_1 & a_0 \end{bmatrix} 的矩阵。

设 f(x)=∑i=0n−1aixif(x)=\sum_{i=0}^{n-1}a_ix^i 没必要拘泥于aia_i 的下标，取第一行依次排开即可，是等价的。

则：det⁡(A)=∏i=0n−1f(ωi)\det(A)=\prod_{i=0}^{n-1}\limits{f(\omega_i)}

即 对于循环矩阵，有快速的求值方式。

LGV引理

在一张 DAG 上，给定 nn 个起点 a1,⋯ ,ana_1,\cdots,a_n ，nn 个终点 b1,⋯ ,bnb_1,\cdots,b_n，求选出 nn 条路径 (ai,bi)​(a_i, b_i)​ 互不相交（不经过同一个点）的方案数。

设 f(a,b)f(a, b) 表示从 DAG 上从 aa 走到 bb 的方案数。

构造矩阵 CC, 满足 ca,b=f(a,b)c_{a, b}=f(a, b)。

LGV引理指出，其方案数为： det⁡(C) \det(C) 考虑任意一个有交方案，都能够对应一种其他方案，对应奇偶排列，这些方案会被抵消。

栗题

Y\mathbb{Y} 轴正半轴上有 nn 个点 (0,a1),(0,a2),⋯ ,(0,an)(0, a_1),(0, a_2), \cdots,(0, a_n)，他们每次可以向右或向下走一格，求最后分别走到 (1,0),(2,0),⋯ ,(n,0)(1, 0), (2, 0), \cdots, (n, 0) 的方案数。 n,ai≤106n, a_i \le 10^6

考虑这里的从 (0,ai)(0, a_i) 到 (j,0)(j, 0) 的方案数为 (ai+jj)\dbinom{a_i + j}{j}

构造行列式为： ∣(a1+11)⋯(a1+nn)⋮⋱⋮(an+11)⋯(an+nn)∣ \begin{vmatrix} \dbinom{a_1+1}{1}&\cdots&\dbinom{a_1+n}{n}\\ \vdots & \ddots& \vdots\\ \dbinom{a_n+1}{1}&\cdots&\dbinom{a_n+n}{n} \end{vmatrix} 对于每一列 jj 提出公因子 1j!​\frac{1}{j!}​，得： 11! 2!⋯n!∣(a1+1)1‾⋯(a1+n)n‾⋮⋱⋮(an+1)1‾⋯(an+1)n‾∣ \frac{1}{1!\ 2!\cdots n!}\begin{vmatrix} (a_1+1)^{\underline{1}}&\cdots&(a_1+n)^{\underline{n}}\\ \vdots & \ddots& \vdots\\ (a_n+1)^{\underline{1}}&\cdots&(a_n+1)^{\underline{n}} \end{vmatrix} 对每一行 ii 提出公因子 (ai+1)(a_i+1) 得到： (a1+1)(a2+1)⋯(an+1)1! 2!⋯n!∣1⋯(a1+n)n−1‾⋮⋱⋮1⋯(an+1)n−1‾∣ \frac{(a_1+1)(a_2+1)\cdots(a_n+1)}{1!\ 2!\cdots n!} \begin{vmatrix} 1&\cdots&(a_1+n)^{\underline{n-1}}\\ \vdots & \ddots& \vdots\\ 1&\cdots&(a_n+1)^{\underline{n-1}} \end{vmatrix} 类似于归纳法的消元方法，注意到每一列都是一系列形式相同的关于 aia_i 的多项式，考虑可以用前面的每一列来消这一列，使得这一列 ii 只剩下第 ii 次项。

最后能得到一个范德蒙行列式，形如： F=∣1a1a12⋯a1n−1⋮⋱⋮1anan2⋯ann−1∣ F=\begin{vmatrix} 1 & a_1 & a_1^2 & \cdots & a_1^{n-1} \\ \vdots & & &\ddots &\vdots\\ 1 & a_n & a_n^2 & \cdots & a_n^{n-1} \\ \end{vmatrix} 范德蒙行列式的值有如下结论： det⁡(F)=∏i<j(aj−ai) \det(F)=\prod_{i < j}(a_j - a_i) 注意按照归纳法推导过程，不难发现其实应该会推导出一个 αF\alpha F 的形式，但是这里的 α\alpha 的值为 1​1​ ，可以忽略。

可以考虑枚举差值 kk ，计算有多少对数字差值为 kk。

记 gig_i 表示有多少 aa 等于 ii，构造 gig_i 的生成函数 G(x)G(x)。

易知：[xk]∑i=kgigi−k[x^k]\sum_{i=k}\limits{g_ig_{i-k}} 就是所求。复杂度为 O(ailog⁡ai)\mathcal{O}(a_i \log a_i)。

📚 Version History

Source Code Change History
v1
🔗 Source Hash: 3fd1a3fd0f4ad654e96bb43673b678d908a04c14ea8b2dd5d370a1b853e60813
Build Logs 
Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「学习总结」正睿 计数选讲.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache/oi-blog_「学习总结」正睿 计数选讲.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../0e8c4dffb6.pdf.md', '-o', 'cache/0e8c4dffb6.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「学习总结」正睿 计数选讲},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「学习总结」正睿 计数选讲}
  \author{Jiayi Su (ShuYuMo)}
  \date{2021-02-01 15:35:06}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  wzy哥哥的一些有趣计数题\textasciitilde{}
  
  \subsection{例题壹}\label{ux4f8bux9898ux58f9}
  
  给定 \(n, m\) ，构造 \(n\) 堆石子，每堆石子的数量
  \(\in[1, 2^m-1]\)，每堆石子数目互不相同。求使得 Nim
  先手必胜的构造方案数。
  
  \(n\le 10^7, m\le 10^9\) 模数：\(10^9 + 7\)
  
  考虑直接后手必胜的情况，即长度为 \(n\) 的序列，异或和为 \(0\)。
  
  设长度为 \(n\) 的方案数为 \(f(n)\)。能够得到如下递推式： \[
  f(n) = (2^m-1)(2^m-2)(2^m-3) \cdots(2^m - n+1)\\
  -f(n - 1)\\
  -(2^m-1)(i-1)f(n-2)
  \] 考虑到前 \((n-1)\) 位置个随意填上互不相同的值域为 \([1, 2^m-1]\)
  的数字。然后减去前面正好填出异或和为 \(0\)
  的方案（因为最后一个位置还要填数字）（即：\(f(n-1)\)）。理论上，最后一个数字应该等于前面
  \((n - 1)\)
  数字的异或和，但是可能不满足互不相同的条件，先枚举不合法的方案最后一个数字是什么，然后枚举和前面哪一个冲突，再乘上
  \(f(n-2)\)。
  
  \subsection{例题贰}\label{ux4f8bux9898ux8d30}
  
  给出 \(n\) 个正整数 \(a_i\)，选出 \(n\) 个正整数 \(b_i\) ，\(n\)
  个正整数 \(d_i\)，满足
  
  \(\forall i \in [1, n], d_i|b_i|a_i\)，求有多少种选法满足
  \(\prod_{i}^n d_i^2 \ge \prod_{i=1}^{n}b_i\)
  
  \(n\le 100, a_i \le 10^9​\)
  
  对于任意一种方案 \(\prod_{i=1}^{n}d_i^2 > \prod_{i=1}^{n}b_i​\)
  
  试想把所有 \(d_i\) 取成 \(\frac{b_i}{d_i}\)，即：
  \(\prod_{i=1}^{n} \frac{b_i^2}{d_i^2} > \prod_{i=1}^{n}b_i\)
  
  即： \(\prod_{i=1}^{n}d_i^2 < \prod_{i=1}^{n}b_i​\)
  
  所以其实 \(\prod_{i=1}^{n}d_i^2 < \prod_{i=1}^{n}b_i\) 和
  \(\prod_{i=1}^{n}d_i^2 > \prod_{i=1}^{n}b_i\) 的方案是一一对应的。
  
  只需要求出 \(\prod_{i=1}^{n}d_i^2=b_i\)
  的方案数即可。这个可以对每一个质因子单独 dp。
  
  \subsection{例题叁}\label{ux4f8bux9898ux53c1}
  
  \href{https://codeforces.com/contest/383/problem/D}{CF383D}
  
  \(n\) 个位置排成一排,有 \(m\)
  个人依次进场选位置,每个人一开始选一个方向,从左到右/从右到左,并选择一个位置,然后按照她选择的方向进入场地,走到这个位置,如果有人,就继续按当前方向往后寻找,知道找到一个空位坐下,如果没有空位,他就会生气.
  
  为每个人确定一个方向和选择的位置。求没有人生气的方案数。
  
  考虑把序列首尾之间连接一个点 \(n+1\)
  转化成一个环，相当于每个人选择一个位置，然后选择一个方向转圈，方案不合法，当且仅当有一个人占据了
  \(n+1\) 这个位置。
  
  因为是一个环，所以任意一个位置都是等价的，所以任意一个位置有人的概率为
  \((1 -\frac{m}{n+1})​\)
  
  答案就是 \((1 - \frac{m}{n + 1})2^m(n + 1) ^ m\)
  
  \subsection{例题肆}\label{ux4f8bux9898ux8086}
  
  \href{/「杂题记录」「CTSC2017」吉夫特}{「杂题记录」「CTSC2017」吉夫特}
  
  \subsection{例题伍}\label{ux4f8bux9898ux4f0d}
  
  \href{/「杂题记录」括号序列（格路计数）}{「杂题记录」括号序列（格路计数）}
  
  \subsection{例题陆}\label{ux4f8bux9898ux9646}
  
  一棵树，每条边的两个端点的大小关系给出，形如 \(a_u > a_v\) 或者
  \(a_u < a_v\)。求有多少种满足条件的排列 \(a\) 。 \(n \le 5000\)
  
  \subsection{例题柒}\label{ux4f8bux9898ux67d2}
  
  给定一个字符串 \(S\)，仅包含 \texttt{\textless{}} 和
  \texttt{\textgreater{}} 两种字符。
  
  你需要计算「使得 \(p_i < p_{i+1}\) \textbf{当且仅当} \(s_i\)为
  \texttt{\textless{}} 的排列 \(p_1, p_2, \cdots p_{n+1}\) 」的数量。
  
  可以发现，答案可能很大，因此你只要输出它对 \(998244353\) 取模的结果。
  
  巧妙容斥。
  
  先不考虑所有 \texttt{\textgreater{}} 的限制，只考虑 \texttt{\textless{}}
  的限制，\texttt{\textgreater{}} 处的偏序关系任意，将一段
  \texttt{\textless{}} 视为连续的一段，设每一连续的一段长度为 \(a_i\)
  ，这样的方案数就是 \(\frac{n!}{\prod_{i}a_i!}\)。
  
  然后显然答案需要减去任意位置为 \texttt{\textless{}} 的情况，对这个
  \texttt{\textless{}} 满足数量容斥即可。
  
  考虑设 \(f(n)\) 表示只考虑前 \(n\) 个数字方案数。
  
  考虑 \(f(n)\) 的答案和 \(f(n-1)\) 的答案的差别，枚举最后一段有多长即可。
  \[
  f(n) = \sum_{i=1}^{i-1}\frac{[S_j = '>']}{(i-j)!}f(i)(-1)^{cnt_{i-1}-cnt_{j}}
  \] 这东西可以分治 \(NTT​\) 优化。
  
  \subsection{例题玐}\label{ux4f8bux9898ux7390}
  
  \(n\) 阶 \textbf{循环矩阵}是一种形如： \[
  A=\begin{bmatrix}
  a_0     &   a_{n-1} &\cdots     &   a_2     &   a_1\\
  a_1     &   a_{0}   &a_{n-1}    &           &   a_2\\
  \vdots  &   a_1     &a_0        &   \ddots  &   \vdots\\
  a_{n-2} &           &\ddots     &   \ddots  &   a_{n-1}\\
  a_{n-1} &   a_{n-2} &\cdots     &   a_1     &   a_0
  \end{bmatrix}
  \] 的矩阵。
  
  设 \(f(x)=\sum_{i=0}^{n-1}a_ix^i\) 没必要拘泥于\(a_i\)
  的下标，取第一行依次排开即可，是等价的。
  
  则：\(\det(A)=\prod_{i=0}^{n-1}\limits{f(\omega_i)}\)
  
  即 对于循环矩阵，有快速的求值方式。
  
  \subsection{LGV引理}\label{lgvux5f15ux7406}
  
  在一张 \texttt{DAG} 上，给定 \(n\) 个起点 \(a_1,\cdots,a_n\) ，\(n\)
  个终点 \(b_1,\cdots,b_n\)，求选出 \(n\) 条路径 \((a_i, b_i)​\)
  互不相交（不经过同一个点）的方案数。
  
  设 \(f(a, b)\) 表示从 \texttt{DAG} 上从 \(a\) 走到 \(b\) 的方案数。
  
  构造矩阵 \(C\), 满足 \(c_{a, b}=f(a, b)\)。
  
  \textbf{LGV引理}指出，其方案数为： \[
  \det(C)
  \]
  考虑任意一个有交方案，都能够对应一种其他方案，对应奇偶排列，这些方案会被抵消。
  
  \subsubsection{栗题}\label{ux6817ux9898}
  
  \(\mathbb{Y}\) 轴正半轴上有 \(n\) 个点
  \((0, a_1),(0, a_2), \cdots,(0, a_n)\)，他们每次可以向右或向下走一格，求最后分别走到
  \((1, 0), (2, 0), \cdots, (n, 0)\) 的方案数。 \(n, a_i \le 10^6\)
  
  考虑这里的从 \((0, a_i)\) 到 \((j, 0)\) 的方案数为
  \(\dbinom{a_i + j}{j}\)
  
  构造行列式为： \[
  \begin{vmatrix}
  \dbinom{a_1+1}{1}&\cdots&\dbinom{a_1+n}{n}\\
  \vdots           & \ddots& \vdots\\
  \dbinom{a_n+1}{1}&\cdots&\dbinom{a_n+n}{n}
  \end{vmatrix}
  \] 对于每一列 \(j\) 提出公因子 \(\frac{1}{j!}​\)，得： \[
  \frac{1}{1!\ 2!\cdots n!}\begin{vmatrix}
  (a_1+1)^{\underline{1}}&\cdots&(a_1+n)^{\underline{n}}\\
  \vdots           & \ddots& \vdots\\
  (a_n+1)^{\underline{1}}&\cdots&(a_n+1)^{\underline{n}}
  \end{vmatrix}
  \] 对每一行 \(i\) 提出公因子 \((a_i+1)\) 得到： \[
  \frac{(a_1+1)(a_2+1)\cdots(a_n+1)}{1!\ 2!\cdots n!}
  \begin{vmatrix}
  1&\cdots&(a_1+n)^{\underline{n-1}}\\
  \vdots           & \ddots& \vdots\\
  1&\cdots&(a_n+1)^{\underline{n-1}}
  \end{vmatrix}
  \] 类似于归纳法的消元方法，注意到每一列都是一系列形式相同的关于 \(a_i\)
  的多项式，考虑可以用前面的每一列来消这一列，使得这一列 \(i\) 只剩下第
  \(i\) 次项。
  
  最后能得到一个\textbf{范德蒙行列式}，形如： \[
  F=\begin{vmatrix}
  1 & a_1 & a_1^2 & \cdots & a_1^{n-1} \\
  \vdots & & &\ddots &\vdots\\
  1 & a_n & a_n^2 & \cdots & a_n^{n-1} \\
  \end{vmatrix}
  \] 范德蒙行列式的值有如下结论： \[
  \det(F)=\prod_{i < j}(a_j - a_i)
  \] 注意按照归纳法推导过程，不难发现其实应该会推导出一个 \(\alpha F\)
  的形式，但是这里的 \(\alpha\) 的值为 \(1​\) ，可以忽略。
  
  可以考虑枚举差值 \(k\) ，计算有多少对数字差值为 \(k\)。
  
  记 \(g_i\) 表示有多少 \(a\) 等于 \(i\)，构造 \(g_i\) 的生成函数
  \(G(x)\)。
  
  易知：\([x^k]\sum_{i=k}\limits{g_ig_{i-k}}\) 就是所求。复杂度为
  \(\mathcal{O}(a_i \log a_i)\)。
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 78.
  
  [1]
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  Missing character: There is no 玐 (U+7390) in font AR PL UKai CN/OT:script=hani;
  language=dflt;!
  [2] [3] [4] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  Output written on .../input.pdf (4 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty
  (.../infwarerr.sty)))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 78.
  
  [1]
  
  Package xeCJK Warning: Unknown CJK family `\CJKttdefault' is being ignored.
  (xeCJK)                
  (xeCJK)                Try to use `\setCJKmonofont[<...>]{<...>}' to define
  (xeCJK)                it.
  
  Missing character: There is no 玐 (U+7390) in font AR PL UKai CN/OT:script=hani;
  language=dflt;!
  [2] [3] [4] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (4 pages).
  Transcript written on .../input.log.
[WARNING] Missing character: There is no 玐 (U+7390) (U+7390) in font AR PL UKai CN/OT:script=hani;